package leetcode;

public class NthDigit {

//	Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
//	 n = 3, return 3. n = 11,1 ~ 9是9位，10的1是第10位，10的0是第11位，所以返回0
//	10是两位，11是俩位
	
	//前九个数都是1位的，然后10到99总共90个数字都是两位的，100到999这900个数都是三位的，那么这就很有规律了，
//	我们可以定义个变量cnt，初始化为9，然后每次循环扩大10倍，再用一个变量len记录当前循环区间数字的位数，
//	另外再需要一个变量start用来记录当前循环区间的第一个数字
	public int findNthDigit(int n){
		long count = 9;
		long start = 1;
		int len = 1;	//初始所有的位数都为1
		while(n > len * count){
			n -= len * count;
			len++;	//逐渐变为2、3、4...位
			count *= 10;
			start *= 10;
		}
		//找到区间之后，我么还需要找到n在位数为len的位置
		//本应该为n / len，但是计数时是从1开始的，所以应该为(n - 1) / len
		//比如n ： 11, 经过上述循环之后, n = 2, len = 2
		//但是11对应的是10，也就是第一个数，因为此时10计数为1，而不是0
		start += (n - 1) / len;
		//此时的start是我们需要的数，但是在start中的位数还没确定接下来，我们需要找到
		//还是以11为例，此时我们找到了start = 10, 1是第10位，所以0是第11位
		//此时n = 2, len = 2, 那么我们怎么得到是第几位数呢
		//就是(n - 1) % len(这里每个数的位是以0作为下标的);
		String string = String.valueOf(start);
		return string.charAt((n - 1) % len) - '0';
	}
}
